The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Packet classification as required for, inter alia, access control lists (ACLs) and forwarding decisions, is a demanding part of switch and router design. The packet classification of a received packet is increasingly becoming more difficult due to ever increasing packet rates and number of packet classifications. For example, ACLs require matching packets on a subset of fields of the packet flow label, with the semantics of a sequential search through the ACL rules. IP forwarding requires a longest prefix match.
Known approaches of packet classification include using custom application-specific integrated circuits (ASICs), custom circuitry, software or firmware controlled processors, binary and ternary content-addressable memories (CAMs). The use of programmable software or firmware have advantages as they provide some level of flexibility, which becomes especially important as new protocols and services are added to existing network. Customers typically desire to use their existing hardware (e.g., routers, switches etc.) to support these new protocols and services. However, known software and firmware implementations are relatively slow, and typically place a performance bound which may be incompatible with new requirements.
A ternary CAM (TCAM) is a special type of fully associative memory which stores data with three logic values: ‘0’, ‘1’ or ‘*’ (don't care). Each TCAM entry includes a value and a mask. These entries are stored in the TCAM in decreasing order of priority, such as in a decreasing order of the length of prefixes. For a given input, the TCAM compares it against all of the entries in parallel, and returns the entry with the highest priority that matches the input lookup word. An entry matches the input lookup word if the input and the entry value are identical in the bits that are not masked out.
When performing prefix inserts, deletes, and route updates, the exact location of the prefix in the TCAM must be known as the location cannot be determined by simply looking up the prefix in the TCAM, because the TCAM in this application is configured to produce a longest prefix match, so there is no guarantee that a lookup operation will produce the desired entry. For example, if a TCAM contains the three entries of “10101011”, “10101010”, and “1010101*” and the entry “1010101*” is to be deleted, a lookup operation will match either “10101011” or “10101010” rather than produce the location of the desired “1010101*” entry. Thus, a Patricia tree (or another variation of the tree/trie data structure) for prefix updates is stored in memory of the programming mechanism.
Thus, in current implementations, the central processor managing these entries typically maintains a Patricia tree (or trie or some variation thereof) in a memory separate from the TCAM or other associative memory. When a prefix entry is inserted to the TCAM, a pointer is created in the Patricia tree node that points to the TCAM location of the prefix. While deleting a prefix, the Patricia tree is traversed to locate the prefix and find its location in the TCAM. This scheme requires up to L operations and a trie data structure needs to be maintained; where L=maximum prefix length (e.g., L=128 for IPv6). Moreover, it may be expensive to realize this in hardware. For example, in some switches, this scheme requires all TCAMs in the system to have identical prefix entries in each location. Otherwise, for each TCAM, the central processor maintains a pointer to the location of a prefix in that TCAM. In the first case, if there are several line cards with different size TCAMs (say, 64K, 128K, 256K and 512K), then they are all limited to contain only 64K prefix entries. In the second case, in order to delete a route table entry from the system, the central processor sends a message specifically for each TCAM. Alternatively, a trie data structure needs to be maintained with each TCAM.
For the reasons presented herein and/or other reasons, new methods and apparatus are needed for using and updating associative memory entries.